{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of 1 Bits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #divide-and-conquer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #分治"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: hammingWeight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #位1的个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为<a href=\"https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E9%87%8D%E9%87%8F\" target=\"_blank\">汉明重量</a>）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。</li>\n",
    "\t<li>在 Java 中，编译器使用<a href=\"https://baike.baidu.com/item/二进制补码/5295284\" target=\"_blank\">二进制补码</a>记法来表示有符号整数。因此，在&nbsp;<strong>示例 3</strong>&nbsp;中，输入表示有符号整数 <code>-3</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 00000000000000000000000000001011\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>输入的二进制串 <code><strong>00000000000000000000000000001011</strong>&nbsp;中，共有三位为 '1'。</code>\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 00000000000000000000000010000000\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>输入的二进制串 <strong>00000000000000000000000010000000</strong>&nbsp;中，共有一位为 '1'。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 11111111111111111111111111111101\n",
    "<strong>输出：</strong>31\n",
    "<strong>解释：</strong>输入的二进制串 <strong>11111111111111111111111111111101</strong> 中，共有 31 位为 '1'。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>输入必须是长度为 <code>32</code> 的 <strong>二进制串</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶</strong>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果多次调用这个函数，你将如何优化你的算法？</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-1-bits](https://leetcode.cn/problems/number-of-1-bits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-1-bits](https://leetcode.cn/problems/number-of-1-bits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['00000000000000000000000000001011', '00000000000000000000000010000000', '11111111111111111111111111111101']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        return bin(n)[2:].count('1')\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        sum = 0\n",
    "        while n:\n",
    "            n &= n - 1\n",
    "            sum += 1\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        count = 0\n",
    "        while n:\n",
    "            count += n & 1\n",
    "            n >>= 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def hammingWeight(self, n: int) -> int:\r\n",
    "        \r\n",
    "        return str(bin(n)).count('1')\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        bits = 0\n",
    "       \n",
    "        while n != 0:\n",
    "            bits+=1\n",
    "            n = n&(n-1)\n",
    "\n",
    "        return bits\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n!=0:\n",
    "            n=n&(n-1)\n",
    "            res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        while n > 0:\n",
    "\n",
    "            ans += n & 1\n",
    "\n",
    "            n >>= 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        # 思路，位运算，如何快速定位最右的 1 位，如何确定已经找到最后一个 1 位\n",
    "        # 技巧：1、使用 n-1 的二进制特性；2、通过逐个消除 1，判断剩余数值是否大于 0 判断是否还存在 1 位\n",
    "        i = 0\n",
    "        while n > 0:\n",
    "            i += 1\n",
    "            n = n & (n-1)\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        # 思路，位运算，如何快速定位最右的 1 位，如何确定已经找到最后一个 1 位\n",
    "        # 技巧：1、使用 n-1 的二进制特性；2、通过逐个消除 1，判断剩余数值是否大于 0 判断是否还存在 1 位\n",
    "        # i = 0\n",
    "        # while n > 0:\n",
    "        #     i += 1\n",
    "        #     n = n & (n-1)\n",
    "        # return i\n",
    "        return bin(n).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def hammingWeight(self, n: int) -> int:\r\n",
    "        s = bin(n)[2:]\r\n",
    "        count = 0\r\n",
    "        for c in s:\r\n",
    "            if(c == '1'):\r\n",
    "                count+=1\r\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        return  (str(bin(n)).count('1'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        num = 0\n",
    "        for i in bin(n):\n",
    "            if i == \"1\":\n",
    "                num = num + 1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n:\n",
    "            res += 1\n",
    "            n &= n - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        stra = str(bin(n)[2:].zfill(32))\n",
    "        print(stra)\n",
    "        return stra.count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        return bin(n).count(\"1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        l = 0\n",
    "        n = int(str(n))\n",
    "        if n == 0 :return 0\n",
    "        if n == 1 :return 1\n",
    "        while n > 1 or n == 0:\n",
    "            print(n)\n",
    "            if n % 2 == 1:\n",
    "                l += 1\n",
    "            n = n // 2\n",
    "            if n == 1:\n",
    "                l += 1\n",
    "                break\n",
    "            \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import ctypes\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        # 位置右移\n",
    "        res = 0\n",
    "        while n:\n",
    "            res += n & 1\n",
    "            n >>= 1\n",
    "        return res\n",
    "'''\n",
    "        res = 0\n",
    "        while n:\n",
    "            res += n & 1\n",
    "            n >>= 1\n",
    "        return res'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(32):\n",
    "            if 1 << i & n > 0:\n",
    "                count += 1\n",
    "        return count\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        ret = sum(1 for i in range(32) if n & (1 << i)) \n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hammingWeight(self, n: int) -> int:\n",
    "        res = 0\n",
    "        while n > 0:\n",
    "            if n & 1:\n",
    "                res += 1\n",
    "            n = n >> 1\n",
    "        return res        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
